/*
  author Sylvain Bertrand <digital.ragnarok@gmail.com>
  Protected by GNU Affero GPL v3 with some exceptions.
  See README at root of alga tree.
*/

/* Very simple range manager */
#include <linux/module.h>
#include <linux/list.h>
#include <linux/slab.h>

#include <alga/alga.h>
#include <alga/rng_mng.h>

static bool have_room_align(u64 *s_aligned, struct rng *mng, struct rng *r,
					struct rng *next_r, u64 sz, u64 align)
{
	u64 gap_start;
	u64 gap_end;

	gap_start = r->s + r->sz;

	if (&next_r->n == &mng->n)
		gap_end = mng->s + mng->sz - 1; /* r is the list tail */
	else
		gap_end = next_r->s - 1;

	*s_aligned = rng_align(gap_start, align);

	if ((*s_aligned + sz - 1) <= gap_end)
		return true;
	return false;
}

static bool first_range(u64 *s_aligned, struct rng *mng, u64 sz, u64 align)
{
	*s_aligned = rng_align(mng->s, align);

	if ((*s_aligned + sz - 1) <= (mng->s + mng->sz - 1))
		return true;
	return false;
}

void rng_mng_init(struct rng *mng, u64 s, u64 sz)
{
	mng->s = s;
	mng->sz = sz;
	INIT_LIST_HEAD(&mng->n);
}
EXPORT_SYMBOL_GPL(rng_mng_init);

void rng_mng_destroy(struct rng *mng)
{
	struct rng *pos;
	struct rng *n;

	list_for_each_entry_safe(pos, n, &mng->n, n) {
		list_del(&pos->n);
		kfree(pos);
	}
}
EXPORT_SYMBOL_GPL(rng_mng_destroy);

int rng_alloc_align(u64 *s_aligned, struct rng *mng, u64 sz, u64 align)
{
	struct rng *new_r;
	struct rng *pos;

	if ((s_aligned == NULL) || (mng == NULL) || (align == 0))
		return -ALGA_ERR;

	if (sz % align != 0)
		return -ALGA_ERR;

	new_r = kzalloc(GFP_KERNEL, sizeof(*new_r));
	if (new_r == NULL)
		return -ALGA_ERR;
	INIT_LIST_HEAD(&new_r->n);

	if (list_empty(&mng->n)) {
		if (!first_range(s_aligned, mng, sz, align)) {
			kfree(new_r);
			return -ALGA_ERR;
		}

		new_r->s = *s_aligned;
		new_r->sz = sz;
		list_add(&new_r->n, &mng->n);
		return 0;
	}

	/* look for aligned room */
	list_for_each_entry(pos, &mng->n, n) {
		struct rng *next;

		next = list_entry(pos->n.next, struct rng, n);
		if (have_room_align(&new_r->s, mng, pos, next, sz, align)) {
			__list_add(&new_r->n, &pos->n, &next->n);
			new_r->sz = sz;
			*s_aligned = new_r->s;
			return 0;
		}
	}
	kfree(new_r);
	return -ALGA_ERR;
}
EXPORT_SYMBOL_GPL(rng_alloc_align);

void rng_free(struct rng *mng, u64 s)
{
	struct rng *pos;

	list_for_each_entry(pos, &mng->n, n) {
		if (pos->s == s) {
			list_del(&pos->n);
			kfree(pos);
			break;
		}
	}
}
EXPORT_SYMBOL_GPL(rng_free);
